// // 堆排序 时间复杂度nlogn (从小到大)
// // 这里是实现了最大堆 升序排序
// // 构建最大堆
// function buildMaxHeap(arr,len) {
//    // 从最后一个非叶子节点开始，自下而上堆化 索引起点和数组索引一样为0
//   // 最后一个叶子节点索引len-1 父节点索引 （len-1-1）/2 
//   // 但是这里 可以直接 len/2  因为在堆调整函数中直接返回了，
//   for (let i = Math.floor(len / 2); i >= 0; i--) {
//     // 对非叶节点做堆调整
//     maxHeapify(arr, i, len);
//   }
// }

// // 堆调整 也就是交换完成之后要变成堆结构
// // 如果根节点小于左右孩子 则下移
// function maxHeapify(arr, i, len) {
//   // 计算某节点与其左右子节点在位置上的关系
//   let left = 2 * i + 1; // 左孩子索引
//   let right = 2 * i + 2; // 右孩子索引
//   let largest = i; // 该子树的根节点
//   // 变成最小堆 只要大于改成小于就可以了
//   // 是否左子节点比当前节点的值更大，而且不能超出数组长度
//   if (left < len && arr[left] > arr[largest]) {
//     largest = left;
//   }
//   // 是否右子节点比当前更大节点的值更大，而且不能超出数组长度
//   if (right < len && arr[right] > arr[largest]) {
//     largest = right;
//   }
//   // 如果三者中，当前节点值不是最大的,把最大的节点放到根节点位置
//   if (largest !== i) {
//     [arr[largest], arr[i]] = [arr[i], arr[largest]];
//     // 继续递归调整
//     maxHeapify(arr, largest, len);
//   }
// }

// // 堆排序   将根节点和最后一个节点交换
// function heapSort(arr) {
//   let len = arr.length;
//   buildMaxHeap(arr, len);
//   // 最大堆构建完成之后 根节点就是最大值，
//   for (let i = len - 1; i > 0; i--) {
//     // 根节点与最后一个节点交换值。
//     [arr[i], arr[0]] = [arr[0], arr[i]];
//     len--;
//     // 在进行对调整。
//     maxHeapify(arr, 0, len);
//   }
//   return arr;
// }

// // 测试用例
// const arr = [2,3,2,6,5,12,2,4,9,10,7,8]
// console.log(heapSort(arr))

function buildMaxHeap(arr) {
  let len = arr.length;
  for (let i = Math.floor(len / 2); i >= 0; i--) {
    maxHeapify(arr, i, len);
  }
}

function maxHeapify(arr, i, len) {
  let left = 2 * i + 1;
  let right = 2 * i + 2;
  let largest = i;
  if (left < len && arr[left] > arr[largest]) {
    largest = left;
  }
  if (right < len && arr[right] > arr[largest]) {
    largest = right;
  }
  if (largest !== i) {
    [arr[largest], arr[i]] = [arr[i], arr[largest]];
    maxHeapify(arr, largest, len);
  }
}

function heapSort(arr) {
  let len = arr.length;
  buildMaxHeap(arr);
  for (let i = len - 1; i >= 0; i--) {
    [arr[i], arr[0]] = [arr[0], arr[i]];
    len--;
    maxHeapify(arr, 0, len);
  }
}

const arr = [1, 3, 4, 2, 2, 2, 7, 1, 15, 12];
buildMaxHeap(arr);
console.log(arr);
heapSort(arr);
console.log(arr);
